module Diccionario (Diccionario, vacio, definir, definirVarias, obtener, claves) where
    
import Maybe
import List
import Arbol23

{- Definiciones de tipos. -}

type Comp clave = clave->clave->Bool
type Estr clave valor = Arbol23 (clave,valor) clave

data Diccionario clave valor = Dicc {cmp :: Comp clave, estructura :: Maybe (Estr clave valor)}
--El comparador es por menor.

{- Funciones provistas por la cátedra. -}

--Inserta un nuevo par clave, valor en una estructura que ya tiene al menos un dato.
insertar::clave->valor->Comp clave->Estr clave valor-> Estr clave valor
insertar c v comp a23 = interceptar (insertarYPropagar c v comp a23) id (\s1 (c1, s2)->Dos c1 s1 s2)

--Maneja el caso de que la segunda componente sea Nothing.
interceptar::(a,Maybe b)->(a->c)->(a->b->c)->c
interceptar (x,y) f1 f2 = case y of
                   Nothing -> f1 x
                   Just z -> f2 x z

{- Inserta una clave con su valor correspondiente. Si se actualiza el indice, el cambio se propaga hacia arriba
   para mantener balanceado el árbol.
   Usamos recursión explicita porque este tipo de recursión no es estructural (no se aplica a todos los hijos). -}
insertarYPropagar::clave->valor->Comp clave->Estr clave valor-> (Estr clave valor, Maybe (clave, Estr clave valor))
insertarYPropagar c v comp a23 = let rec = insertarYPropagar c v comp in case a23 of
    --Si es hoja, elegimos la máxima de las claves y propagamos el balanceo hacia arriba.
    Hoja (ch,vh) -> if comp c ch 
                then (Hoja (c,v), Just (ch, Hoja (ch,vh)))
                else (Hoja (ch, vh), Just (c, Hoja (c,v)))
    {- Si el actual es Nodo-Dos, o se queda en forma Nodo-Dos o se transforma en 
       Nodo-Tres; no puede ocurrir que haya propagación hacia arriba (retornamos Nothing). -}
    Dos c1 a1 a2 -> (if comp c c1
                then 
                -- La clave c va del lado izquierdo.
                    interceptar (rec a1) 
                        (\s1 -> Dos c1 s1 a2)
                        (\s1 (c3, s2) -> Tres c3 c1 s1 s2 a2)
                else 
                -- La clave c va del lado derecho.
                    interceptar (rec a2) 
                        (\s1 -> Dos c1 a1 s1)
                        (\s1 (c3, s2) -> Tres c1 c3 a1 s1 s2), Nothing)
    {- Nodo-tres sólo propaga si de abajo propagan, los tres casos son muy similares
       Sólo cambia en que árbol se inserta. -}
    Tres c1 c2 a1 a2 a3 -> if comp c c1
                then 
                    -- La clave debe ir en el primer árbol.
                    interceptar (rec a1) 
                        (\s1 -> (Tres c1 c2 s1 a2 a3, Nothing))
                        (\s1 (c3, s2) -> (Dos c3 s1 s2, Just(c1, Dos c2 a2 a3)))
                else if comp c c2
                then 
                    -- La clave debe ir en el árbol del medio.
                    interceptar (rec a2) 
                        (\s1 -> (Tres c1 c2 a1 s1 a3, Nothing))
                        (\s1 (c3, s2) -> (Dos c1 a1 s1, Just(c3, Dos c2 s2 a3)))
                else 
                    --La clave debe ir en el último árbol.
                    interceptar (rec a3) 
                        (\s1 -> (Tres c1 c2 a1 a2 s1, Nothing))
                        (\s1 (c3, s2) -> (Dos c1 a1 a2, Just(c2, Dos c3 s1 s2)))

{- Busca sobre la estructura del diccionario en tiempo logarítmico.
   En cada nivel compara el valor a buscar contra los elementos
   del índice para definir por dónde se sigue buscando. -}
buscar :: Eq clave => clave -> Comp clave -> Estr clave valor -> Maybe valor
buscar k comp = foldA23 fHoja fDos fTres
        where   fHoja (c,v) | c == k = Just v
                            | otherwise = Nothing
                fDos c searchL searchR  | comp k c = searchL
                                        | otherwise = searchR
                fTres c1 c2 searchL searchM searchR | comp k c1 = searchL
                                                    | comp k c2 = searchM
                                                    | otherwise = searchR

--Se asume que la lista no tiene claves repetidas.
definirVarias::[(clave,valor)]->Diccionario clave valor->Diccionario clave valor
definirVarias = (flip.foldr.uncurry) definir

{- Funciones a implementar. -}

{- Diccinario vacío
   Se construye con el comparador y una estructura "nula" -}
vacio::Comp clave->Diccionario clave valor
vacio comp = Dicc comp Nothing

{- Define un clave en el diccionario
   Si estaba vacío, inicializa el árbol con un único elemento
   Si no inserta el elemento en el árbol manteniendo el invariante de Arbol23 -}
definir::clave->valor->Diccionario clave valor->Diccionario clave valor
definir c v (Dicc comp estr) =  case estr of
    Nothing -> Dicc comp (Just(Hoja (c,v)))
    Just a ->  Dicc comp (Just(insertar c v comp a))

{- Retorna el valor asociado a una clave del diccionario, si existe.
   Si el diccionario es vacío devuelve Nothing.
   Si no, el resultado depende de la búsqueda dentro del árbol. -}
obtener::Eq clave=>clave->Diccionario clave valor->Maybe valor
obtener c dicc = if isNothing (estructura dicc) then Nothing else buscar c (cmp dicc) (fromJust (estructura dicc))

--Retorna las claves del diccionario.
claves::Diccionario clave valor->[clave]
claves (Dicc _ estr) = case estr of 
    Nothing -> []
    Just a -> map fst (hojas a)